package dataStructure.study.linkedList;

/**
 * Author: shangsf
 * Date: 2021/3/28 14:46
 * Description:单链表:带头和尾
 */
public class SingleLinkedList2<T> {
    private Node<T> head=null;
    private Node<T> tail=null;
    private int size;


    public void addFirst(T data){
        Node<T> node=new Node<T>(data);
        if(head==null){
            head=node;
            tail=head;
        }else {
            node.next=head;
            head=node;
        }
        size++;
    }

    public void addLast(T data){
        Node<T> node=new Node<T>(data);
        if(head==null){
            head=node;
            tail=head;
        }else {
            tail.next=node;
            tail=node;
        }
        size++;
    }

    public void add(T data){
        addLast(data);
    }

    public void remove(T data){
        if(null==data){
            return;
        }
        Node<T> prev=null;
        Node<T> node=head;
        if(null==node){
            return;
        }
        for(;node!=null;node=node.next){
            if(node.data.equals(data)){
                if(prev==null){//头节点
                    head=head.next;
                }else {
                    prev.next=node.next;
                    if(node.next==null){
                        tail=prev;
                    }
                }
                --size;
                break;
            }
            prev=node;
        }
    }

    public T remove(){
        if(head==null){
            return null;
        }
        Node<T> node=head;
        head=head.next;
        size--;
        return node.data;
    }

    public T getFirst(){
        return head!=null?head.data:null;
    }

    public T getLast(){
        return tail!=null?tail.data:null;
    }

    public T get(int index){
        if(index>=size){
            return null;
        }
        if(index==0){
            return getFirst();
        }else if(index==size-1){
            return getLast();
        }
        Node<T> node=head;
        if(node==null){
            return null;
        }
        int count=0;
        while (node.next!=null){
            count++;
            node=node.next;
            if(count==index){
                return node.data;
            }
        }
        return null;
    }

    public int size(){
        return size;
    }


    public static class Node<T>{
        public T data;
        public Node<T> next;

        public Node(T t){
            data=t;
            next=null;
        }
    }
}
